package ch04;

public class UF {
    private int[] id;//父链接数组（由触点索引）
    private int[] sz;//（有触点索引的）各个根节点所对应的分量的大小
    private int count; //连通分量的数量

    public UF(int size)
    {
        id = new int[size];
        sz = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    public boolean connected(int v, int w) {
        return find(v) == find(w);
    }

    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int fp = find(p);
        int fq = find(q);
        if (fp == fq) {
            return;
        }
        if (sz[fp] > sz[fq]) {
            id[fq] = fp;
            sz[fp] += sz[fq];
        }else{
            id[fp] = fq;
            sz[fq] += sz[fp];
        }
        count--;
    }

}
